import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

public class Test {
    // 题目1 ：不同的二叉搜索树
    // 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                G[i] += (G[j - 1] * G[i - j]);
            }
        }
        return G[n];
    }

    // 题目 2：路径总和
    // 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 target 。如果存在，返回 true ；否则，返回 false 。
    //
    //叶子节点 是指没有子节点的节点。
    public boolean hasPathSum1(TreeNode root, int target) {
        if(root == null){
            return false;
        }

        if(root.left == null && root.right == null && root.val == target){
            return true;
        }

        int t = target - root.val;
        return hasPathSum(root.left, t) || hasPathSum(root.right, t );
    }

    // 稍微优化的版本
    public boolean hasPathSum(TreeNode root, int target) {
        if(root == null){
            return false;
        }

        if(root.left == null && root.right == null ){
            return root.val == target;
        }

        int t = target - root.val;
        return hasPathSum(root.left, t) || hasPathSum(root.right, t );
    }

    // 题目 3：路径总和 II
//    给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//    叶子节点 是指没有子节点的节点。

    List<List<Integer>> sum = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        allPath(root, targetSum);
        return sum;
    }

    private void allPath(TreeNode root, int targetSum){
        if(root == null){
            return;
        }

        path.add(root.val);
        targetSum -= root.val;

        if(root.left == null && root.right == null && targetSum == 0){
            sum.add(new LinkedList<Integer>(path));
        }

        allPath(root.left, targetSum);
        allPath(root.right, targetSum);

        path.pollLast();
    }

    // 题目 4 ：二叉树的所有路径
    // 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
    //
    //叶子节点 是指没有子节点的节点。
    List<String> allPath = new LinkedList<>();
    Deque<String> path1 = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null){
            return allPath;
        }

        searchPath(root);

        return allPath;
    }

    private void searchPath(TreeNode root){
        if(root == null){
            return;
        }

        path1.offer(root.val+"");

        if(root.left == null && root.right == null){
            StringBuilder temp = new StringBuilder();
            for(String s : path1){
                temp.append(s+"->");
            }
            int start = temp.lastIndexOf("->");
            int end = start + 2;
            temp.delete(start, end);
            allPath.add(temp.toString());
        }
        searchPath(root.left);
        searchPath(root.right);

        path.pollLast();
    }

    // 题目 5：验证二叉搜索树
    // 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    //
    //有效 二叉搜索树定义如下：
    //
    //节点的左子树只包含 小于 当前节点的数。
    //节点的右子树只包含 大于 当前节点的数。
    //所有左子树和右子树自身必须也是二叉搜索树。
    // 方法一： 递归
    public boolean isValidBST(TreeNode root) {
        return isSubValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isSubValidBST(TreeNode root, long lower, long upper){
        if(root == null){
            return true;
        }

        if(root.val <= lower || root.val >= upper){
            return false;
        }

        return isSubValidBST(root.left, lower, root.val) && isSubValidBST(root.right, root.val, upper);
    }

    // 方法二：中序遍历
    Deque<TreeNode> queue = new LinkedList<>();
    public boolean isValidBST1(TreeNode root) {
        if(root == null){
            return true;
        }

        boolean left = isValidBST1(root.left);
        if(!queue.isEmpty()){
            if(root.val <= queue.peekLast().val){
                return false;
            }
        }
        queue.offer(root);

        boolean right = isValidBST1(root.right);

        return left && right;
    }

    // 中序遍历的优化
    // 使用一个变量来记录中序遍历的前一个值，而不是用一个集合！
    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {
        if(root == null){
            return true;
        }

        if(!isValidBST2(root.left)){
            return false;
        }

        if(root.val <= pre){
            return false;
        }

        pre = root.val;

        return isValidBST2(root.right);
    }

    // 题目 6：二叉树的最小深度
    // 给定一个二叉树，找出其最小深度。
    //
    //最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
    //
    //说明：叶子节点是指没有子节点的节点。

    public int minDepth1(TreeNode root) {
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        int left = minDepth1(root.left);
        int right = minDepth1(root.right);
        if(left == 0){
            return right + 1;
        }
        if(right == 0){
            return left + 1;
        }
        return Math.min(left, right) + 1;
    }

    // 来自题解的优化
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1;
    }

    // 题目7 ：平衡二叉树
    // 给定一个二叉树，判断它是否是高度平衡的二叉树。
    //
    //本题中，一棵高度平衡二叉树定义为：
    //
    //一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
    








}
